
/**
 * 
 * 矩阵最长递增路径
 * 
 * 描述

给定一个 n 行 m 列矩阵 matrix ，矩阵内所有数均为非负整数。 你需要在矩阵中找到一条最长路径，使这条路径上的元素是递增的。并输出这条最长路径的长度。
这个路径必须满足以下条件：

1. 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。
2. 你不能走重复的单元格。即每个格子最多只能走一次。

数据范围：
1
≤
n
,
m
≤
1000
1≤n,m≤1000，
0
≤
m
a
t
r
i
x
[
i
]
[
j
]
≤
1000
0≤matrix[i][j]≤1000
进阶：空间复杂度 
O
(
n
m
)
O(nm) ，时间复杂度 
O
(
n
m
)
O(nm)

例如：当输入为[[1,2,3],[4,5,6],[7,8,9]]时，对应的输出为5，
其中的一条最长递增路径如下图所示：
 */
public class 矩阵最长递增路径 {
    
    public static void main(String[] args) {

    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public static int solve (int[][] matrix) {
        // write code here

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] memo = new int[rows][cols];
        int maxLength = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                maxLength = Math.max(maxLength, dfs(matrix, i, j, memo));
            }
        }
        return maxLength;
    }

    private static int dfs(int[][] matrix, int i, int j, int[][] memo) {
        if (memo[i][j]!= 0) {
            return memo[i][j];
        }
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int maxLen = 1;
        for (int[] dir : directions) {
            int newI = i + dir[0];
            int newJ = j + dir[1];
            if (newI >= 0 && newI < matrix.length && newJ >= 0 && newJ < matrix[0].length && matrix[newI][newJ] > matrix[i][j]) {
                maxLen = Math.max(maxLen, 1 + dfs(matrix, newI, newJ, memo));
            }
        }
        memo[i][j] = maxLen;
        return maxLen;
    }
}
